import org.junit.Test;

import java.util.HashSet;
import java.util.LinkedList;

public class leetCodeResult0928 {

    @Test
    public void test() {
        int[] a = {1, 2, 3, 4,5};
        ListNode listNode = buildListNode(a);
        oddEvenList(listNode);
    }

    /**
     * 构建一个函数将数组元素以此排列建成一个链表,返回这个链表的头结点
     *
     * @param a
     * @return
     */
    private ListNode buildListNode(int[] a) {
        ListNode head = new ListNode(a[0]);
        ListNode copyHead = head;
        for (int i = 1; i < a.length; i++) {
            copyHead.next = new ListNode(a[i]);
            copyHead = copyHead.next;
        }
        return head;
    }

    public static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }

    /**
     * 141. 环形链表
     * 给你一个链表的头节点 head ，判断链表中是否有环。
     * <p>
     * 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
     * <p>
     * 如果链表中存在环 ，则返回 true 。 否则，返回 false 。
     */
    public boolean hasCycle(ListNode head) {
        HashSet<ListNode> listNodes = new HashSet<>();
        while (head != null) {
            if (listNodes.contains(head)) {
                return true;
            }
            listNodes.add(head);
            head = head.next;
        }
        return false;
    }

    /**
     * 142. 环形链表 II
     * 中等
     * 相关标签
     * premium lock icon
     * 相关企业
     * 给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
     * <p>
     * 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
     * <p>
     * 不允许修改 链表。
     */
    public ListNode detectCycle(ListNode head) {
        HashSet<ListNode> listNodes = new HashSet<>();
        listNodes.add(head);
        while (head != null && head.next != null) {
            if (listNodes.contains(head.next)) {
                return head.next;
            }
            listNodes.add(head.next);
            head = head.next;
        }
        return null;
    }

    /**
     * 2095. 删除链表的中间节点
     * 中等
     * 相关标签
     * premium lock icon
     * 相关企业
     * 提示
     * 给你一个链表的头节点 head 。删除 链表的 中间节点 ，并返回修改后的链表的头节点 head 。
     * <p>
     * 长度为 n 链表的中间节点是从头数起第 ⌊n / 2⌋ 个节点（下标从 0 开始），其中 ⌊x⌋ 表示小于或等于 x 的最大整数。
     * <p>
     * 对于 n = 1、2、3、4 和 5 的情况，中间节点的下标分别是 0、1、1、2 和 2 。
     */
    public ListNode deleteMiddle(ListNode head) {
        LinkedList<ListNode> listNodes = new LinkedList<>();
        while (head != null) {
            listNodes.add(head);
            head = head.next;
        }
        if (listNodes.size() == 1) {
            return null;
        }
        int middleIndex = listNodes.size() / 2;
        ListNode delNode = listNodes.get(middleIndex);
        ListNode preDelNode = listNodes.get(middleIndex - 1);
        preDelNode.next = delNode.next;
        return listNodes.get(0);
    }

    /**
     * 328. 奇偶链表
     * 中等
     * 相关标签
     * premium lock icon
     * 相关企业
     * 给定单链表的头节点 head ，将所有索引为奇数的节点和索引为偶数的节点分别分组，保持它们原有的相对顺序，然后把偶数索引节点分组连接到奇数索引节点分组之后，返回重新排序的链表。
     * <p>
     * 第一个节点的索引被认为是 奇数 ， 第二个节点的索引为 偶数 ，以此类推。
     * <p>
     * 请注意，偶数组和奇数组内部的相对顺序应该与输入时保持一致。
     * <p>
     * 你必须在 O(1) 的额外空间复杂度和 O(n) 的时间复杂度下解决这个问题。
     */
    public ListNode oddEvenList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode jNode = head;
        ListNode firstjNode = head;
        ListNode oNode = head.next;
        ListNode firstoNode = head.next;
        ListNode jNodeNext , oNodeNext;
        ListNode jLastNode = new ListNode(1);
        ListNode oLastNode = new ListNode(1);
        int count = 0; //计数链表遍历的节点数
        while (head != null) {
            if (count % 2 == 0) {
                jNodeNext = head;
                if (jNode != jNodeNext) {
                    jNode.next = jNodeNext;
                    jNode = jNodeNext;
                }
                if (jNodeNext.next == null || jNodeNext.next.next == null) {
                    jLastNode = jNodeNext;
                }
            }
            if (count % 2 == 1) {
                oNodeNext = head;
                if (oNode != oNodeNext) {
                    oNode.next = oNodeNext;
                    oNode = oNodeNext;
                }
                if (oNodeNext.next != null && oNodeNext.next.next == null) {
                    oLastNode = oNode;
                }
            }
            head = head.next;
            count++;
        }
        oLastNode.next = null;
        jLastNode.next = firstoNode;
        return firstjNode;
    }

    /**
     * 2130. 链表最大孪生和
     * 中等
     * 相关标签
     * premium lock icon
     * 相关企业
     * 提示
     * 在一个大小为 n 且 n 为 偶数 的链表中，对于 0 <= i <= (n / 2) - 1 的 i ，第 i 个节点（下标从 0 开始）的孪生节点为第 (n-1-i) 个节点 。
     *
     * 比方说，n = 4 那么节点 0 是节点 3 的孪生节点，节点 1 是节点 2 的孪生节点。这是长度为 n = 4 的链表中所有的孪生节点。
     * 孪生和 定义为一个节点和它孪生节点两者值之和。
     *
     * 给你一个长度为偶数的链表的头节点 head ，请你返回链表的 最大孪生和 。
     */
    public int pairSum(ListNode head) {
        int result = Integer.MIN_VALUE;
        LinkedList<ListNode> listNodes = new LinkedList<>();
        while (head != null) {
            listNodes.add(head);
            head = head.next;
        }
        for (int i = 0; i <= listNodes.size() / 2 - 1; i++) {
            result = Math.max(result, listNodes.get(i).val + listNodes.get(listNodes.size() - 1 - i).val);
        }
        return result;
    }
}
